#include<vector>
using namespace std;

class Solution {
private:
    vector<int> sums;

public:
    Solution(vector<int>& w):sums(w.size()) {
        for (int i = 0; i < w.size(); ++i) {
            sums[i] = w[i];
            if (i != 0)
                sums[i] += sums[i - 1];
        }
    }

    int pickIndex() {
        int index = rand() % sums.back() + 1;
        int left = 0, right = sums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (sums[mid] == index) {
                left = mid;
                break;
            }
            if (sums[mid] > index)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */